package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * 988. 从叶结点开始的最小字符串
 *
 * @Author liw
 * @Date 2021/5/21 16:09
 * @Version 1.0
 */
public class SmallestFromLeaf {

    public static void main(String[] args) {


        StringBuilder sb = new StringBuilder();
        sb.append(1);
        sb.append(2);
        sb.reverse();
        System.out.println(sb);

    }

    private String min = null;

    public String smallestFromLeaf(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        find(root, sb);
        return sb.append(min).reverse().toString();
    }

    private void find(TreeNode node, StringBuilder sb){
        sb.append((char) (node.val + 'a'));
        if (node.left == null && node.right == null) {
            String value = sb.toString();
            if (min == null) {
                min = value;
            } else {
                min =compareTo(min, value) <= 0 ? min : value;
            }
            sb.deleteCharAt(sb.length() - 1);
            return;
        }
        if (node.left != null) {
            find(node.left, sb);
        }
        if (node.right != null) {
            find(node.right, sb);
        }
        sb.deleteCharAt(sb.length() - 1);
    }

    public int compareTo(String a, String b) {
        int len1 = a.length() - 1;
        int len2 = b.length() - 1;
        char[] v1 = a.toCharArray();
        char[] v2 = b.toCharArray();
        while (len1 >= 0 && len2 >= 0) {
            char c1 = v1[len1--];
            char c2 = v2[len2--];
            if (c1 != c2) {
                return c1 - c2;
            }
        }
        return len1 - len2;
    }

}
